package jweslley.ProblemSetVolumes.VolumeIII;

import java.math.BigInteger;
import java.util.Scanner;

/**
 * http://icpcres.ecs.baylor.edu/onlinejudge/external/3/374.html
 * 
 * @author Jonhnny Weslley
 * @version 1.00, 15/10/2008
 */
public class BigMod {

	static final BigInteger _0 = new BigInteger("0");
	static final BigInteger _1 = new BigInteger("1");
	static final BigInteger _2 = new BigInteger("2");


	static long mod(long x, long y, long m) {
		return ((x % m) * (y % m)) % m;
	}

	public static void main(String[] args) {
		System.out.println(mod(11, 6, 3));
		StringBuilder out = new StringBuilder();
		Scanner in = new Scanner(System.in);

		long b, p, m;
		while (in.hasNext()) {
			b = in.nextLong();
			p = in.nextLong();
			m = in.nextLong();
			if (in.hasNextLine())
				in.nextLine();

//			out.append(power(b, p).mod(m)).append('\n');
		}
		System.out.print(out);
	}

	public static void smain(String[] args) {
		StringBuilder out = new StringBuilder();
		Scanner in = new Scanner(System.in);
		
		BigInteger b, p, m;
		while (in.hasNext()) {
			b = new BigInteger(in.nextLine());
			p = new BigInteger(in.nextLine());
			m = new BigInteger(in.nextLine());
			if (in.hasNextLine())
				in.nextLine();
			
			out.append(power(b, p).mod(m)).append('\n');
		}
		System.out.print(out);
	}
	/**
	 * Calculates n to the p power, where p is a positive number. 
	 * http://www.algorithmist.com/index.php/Repeated_Squaring
	 * <pre>
	 *
	 * func power( var n as integer, var p as integer )
	 *    if p = 0 return 1
	 *    if p = 1 return n
	 *    if p is odd
	 *      return n * power( n * n, (p-1) / 2 )
	 *    else
	 *      return power( n * n, p / 2 )
	 *  end func
	 */
	static BigInteger power(BigInteger n, BigInteger p) {
		if (p.equals(_0))
			return _1;
		if (p.equals(_1))
			return n;
		if (p.mod(_2).equals(_1))
			return n.multiply(power(n.multiply(n), (p.subtract(_1)).divide(_2)));
		return power(n.multiply(n), p.divide(_2));
	}

}
